package arraysStudy;

/**
 * 数组类型的题就是利用数组连续存储，可以随机存储的特性。比如回文，删除重复值，扩充字符串等。
 */
public class ArrayStudy01 {

    /**
     *在一个长度为n的数组里的所有数字都在0～n-1的范围内。
     * 数组中某些数字是重复的，但不知道有几个数字重复了,
     * 也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
     * 例如，如果输入长度为7的数组{2,3,1, 0,2,5,3}，那么对应的输出是重复的数字2或者3。
     * @param args
     */
    public static void main(String[] args) {
        int[] num = {2,3,1, 0,2,5,3};
        test02(num);
//        System.out.println("=========");
//        for (int i = 0; i < num.length; i++){
//            System.out.println(num[i]);
//        }
    }

    //方法一：进行冒泡排序，排序过程中确定重复值时间复杂度o(n^2)，空间复杂度o(1)
    public static void test01(int[] num){
        int temp, j;
        //冒泡的次数
        for (int i = 0; i < num.length -1; i++){
            for (j = 0; j < num.length - i -1; j++){
                if (num[j] > num[j+1]){
                    temp = num[j];
                    num[j] = num[j+1];
                    num[j+1] = temp;
                }
            }
            if (j < num.length-1){
                if (num[j] == num[j+1]){
                    System.out.println(num[j]);
                    return;
                }
            }
        }
    }
    //方法二：利用hash散列的碰撞的原理进行查找hash函数为y=x，充分利用“在一个长度为n的数组里的所有数字都在0～n-1的范围内”
    //这一条件。时间复杂度为o(n)，空间复杂度为o(n)
    //所有的值都回到自己的位置
    public static void test02(int[] num){
        int temp;
        for (int i = 0; i < num.length; i++){
            while (num[i] != i){
                if (num[i]==num[num[i]]){
                    System.out.println(num[i]);
                    return;
                }
                temp = num[num[i]];
                num[num[i]] = num[i];
                num[i]=temp;
            }
        }
    }
}
